#include <vector>
#include <algorithm>
#include <queue>

using namespace std;


class Solution {
public:
    // 【DFS 回溯 + 剪枝】
    // 先把树状图画出来！
    // 对于每个 sub-problem 节点，其可派生出 out-edge 的 coin 值
    // 必须小于等于其 in-edge 的 coin 值，如此可以排除很多重复计算！
    // (依然太慢，超出时间限制)
    int count = 0;
    int changeDFS(int amount, vector<int>& coins) {
        sort(coins.begin(), coins.end());
        dfs(amount, coins, coins.size()-1);
        return count;
    }

    void dfs(int amount, vector<int>& coins, int upper) {
        if (amount == 0) {
            count++;
            return;
        }
        for (int i=0; i<=upper; ++i) {
            int coin = coins[i];
            if (amount-coin >= 0) {
                dfs(amount-coin, coins, i);
            }
        }
    }

    // 【动态规划解法】
    //     外部为 coins 循环，可以确保遍历 coin 面额的顺序
    //     当你遍历到第 j 个硬币时，你已经不可能再用到第
    //     1...j-1 个硬币，因此确保了我们不会出现重复，即
    //     不会出现 3 = 1 + 2 和 3 = 2 + 1 的情况
    //     (求的是组合 combinations，而不是排列 arrangements)
    // Aside: 类似于 70.爬楼梯 问题，同时也有区别！
    // 时间复杂度：O (amount * coins.size())
    // 空间复杂度：O (amount)
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1);
        dp[0] = 1;
        for (int c : coins) {
            for (int i=c; i<=amount; ++i) {
                dp[i] += dp[i-c];
            }
        }
        return dp[amount];
    }
};
